1. Field of the Invention
The present invention generally relates to the interconnection of processing elements to form massively parallel computer systems and, more particularly, to a method of interconnecting an unlimited number of processing elements in such a way that the number of connections per element can be balanced against the network diameter. The invention specifically provides non-binary hypercube networks.
2. Description of the Prior Art
As the cost of computer elements declines, the possibility of building very large networks is being realized. Ralph Duncan in "A Survey of Parallel Computer Architectures", Computer, February 1990, pp. 5 to 16, reviews alternative approaches to parallel processing. One class of parallel architecture described by Duncan involves multiple processors autonomously executing diverse instructions on diverse data, which Duncan classifies as MIMD for multiple instruction, multiple data streams. Within this class of parallel architecture are the ring, mesh, tree, and hypercube topologies. The ring topology is characterized as having a communication diameter of N/2 where N is the number of nodes. The communication diameter is defined as the worst case path length. In contrast, a two-dimensional mesh topology typically has a communication diameter of 2(N-1) where, again, N is the number of nodes, and this is also the typical communication diameter of tree topologies, although in both cases strategies have been employed to reduce the communication diameters.
Of these known network topologies, the hypercube has some interesting topological properties. A Boolean n-cube or "hypercube" topology uses N=2" processors arranged in an n-dimensional array. Each node, or processor, in the array has n=log.sub.2 N bidirectional links to adjacent nodes. FIG. 1 illustrates hypercubes for n=2,3,4. Examples of existing hypercube machines include Caltech's CosmicCube, Intel's iPSC/2 and NCube's Ncube/10. Descriptions of these and other hypercube computer systems are provided by John P. Hayes et al. in "Hypercube Supercomputers", Proceedings of the IEEE, vol. 77, no. 12, December 1989, pp. 1829 to 1841. Ophir Frieder in "Multiprocessor Algorithms for Relational-Database Operations on Hypercube Systems", Computer, November 1990, pp. 13 to 28, provides a tutorial on hypercube systems, particularly as database engines. Hayes et al. list a variety of representative applications for hypercube computers.
With specific reference to FIG. 1, note the numbering convention for the addresses of the nodes. For n=2, there are four nodes (N=2.sup.2) with addresses 00, 10, 01, and 11. Each node is connected to two other nodes, and the rule applied is that each node is connected to an adjacent node having an address which differs by only one bit. For n=3, there are eight nodes (N=2.sup.3) with addresses 000, 001, 010, 011, 100, 101, 110, and 111, but the connection scheme is the same with, for example, node 000 being connected to nodes 001, 010 and 100. There are sixteen nodes for the case where n=4 (N=2.sup.4), but still the same connection scheme is employed. Laxmi N. Bhuyan and Dharma P. Agrawal in "Generalized Hypercube and Hyperbus Structures for a Computer Network", IEEE Transactions on Computers, vol. c-33, no. 4, April 1984, pp. 323-333, describe a generalization of the binary hypercube to a variable radix numbering. In this scheme, the nodes of a network are numbered in a system in which each digit of the number can be based on a different radix. Nodes are connected whenever the resulting node addresses differ in exactly one digit.
While hypercube architectures offer some very attractive topological properties, as these networks go beyond a few thousand nodes, the numbers of connections per node and path lengths grow in fixed ways. If either connections per node or path lengths become too large for a given technology, the designer is forced to develop new network algorithms from scratch. These new ad hoc topologies may then adversely effect the performance of existing programs that ran well on smaller networks with older topologies.